
package dovs.phases;

import dovs.*;
import dovs.analysis.*;
import dovs.node.*;
import dovs.instructions.*;

import java.util.*;

/**
 * Compiler phase to calculate the maximum number of locals and temporary stack
 * locations needed for each method.
 */
public aspect Limits extends DepthFirstAdapter {
	public static int sum_stack = 0;
	
	/**
	 * The maximum expression stack height obtainable during execution of the
	 * method
	 */
	public int ABody.max_stack;
	/** The number of local variables used in the method */
	public int ABody.max_locals;

	private void verifyError(String message) {
		if (dovs.Main.noverify) {
			System.err.println("Verify warning: " + message);
		} else {
			throw new InternalCompilerError(message);
		}
	}

	@Override 
	public void caseAMethodDecl(AMethodDecl method) {
		boolean is_static = method.isStatic();
		if (method.getBody() != null) {
			computeLimits(method.getFormals(), method.getBody(), is_static);
		}
	}

	@Override 
	public void caseAConstructorDecl(AConstructorDecl constructor) {
		computeLimits(constructor.getFormals(), constructor.getBody(), false);
	}

	private void computeLimits(List<ALocalDecl> formals, ABody body, boolean is_static) {
		// Build label target map
		Map<Label,ListIterator<Instruction>> label_target = new HashMap<Label,ListIterator<Instruction>>();
		LinkedList<Label> label_queue = new LinkedList<Label>();
		Map<Label,Integer> label_height = new HashMap<Label,Integer>();
		ListIterator<Instruction> lit = body.instructions.listIterator();
		while (lit.hasNext()) {
			Instruction i = lit.next();
			if (i instanceof Ilabel) {
				Label l = ((Ilabel)i).getLabel();
				label_target.put(l, body.instructions.listIterator(lit.nextIndex()));
			}
		}

		// Find maximum local index amongst all instructions
		int max_locals = formals.size()+(is_static ? 0 : 1);
		for (Instruction i : body.instructions) {
			if (i.localAccess()+1 > max_locals) {
				max_locals = i.localAccess()+1;
			}
		}

		// Find maximum stack height amongst reachable instructions
		int max_stack = 0;
		int stack = 0;
		lit = body.instructions.listIterator();
		do {
			while (lit.hasNext()) {
				Instruction i = lit.next();
				if (i instanceof Ilabel) {
					Label label = ((Ilabel)i).getLabel();
					if (label_height.containsKey(label)) {
						int lheight = label_height.get(label);
						if (lheight != stack) {
							verifyError("Stack height does not match at " + label +": (" + lheight + " != " + stack + ")");
						}
						break;
					} else {
						label_height.put(label, stack);
					}
				}
				stack += i.stackChange();
				if (stack < 0) {
					verifyError("Negative stack height at " + i.toAsm() + " (" + stack + ")");
				}
				if (stack > max_stack) {
					max_stack = stack;
				}
				if (i.canJump()) {
					Label target = i.getTarget();
					if (!label_height.containsKey(target)) {
						label_queue.add(target);
						label_height.put(target, stack);
					} else {
						int lheight = label_height.get(target);
						if (lheight != stack) {
							verifyError("Stack height does not match at " + target + ": (" + lheight + " != " + stack + ")");
						}
					}
				}
				if (!i.canFallThrough()) {
					break;
				}
			}

			if (!label_queue.isEmpty()) {
				Label l = label_queue.removeFirst();
				lit = label_target.get(l);
				stack = label_height.get(l);
			} else {
				break;
			}
		} while (true);

		// Store maximums
		body.max_stack = max_stack;
		body.max_locals = max_locals;
		sum_stack += max_stack;
	}

}
